package practice_2025_10.practice_10_11;

import java.util.*;
class Solution {
    /**
     * 前 k 个高频元素
     * 优先级队列
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int num: nums) {
            hash.put(num, hash.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((v1, v2) -> (hash.get(v1) - hash.get(v2)));
        for(Integer key: hash.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
            } else {
                int tmp = queue.peek();
                if (hash.get(key) > hash.get(tmp)) {
                    queue.poll();
                    queue.add(key);
                }
            }
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }

    /**
     * 三数之和
     * 双指针
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int i = 0, len = nums.length;
        while(i < len - 1) {
            int target = -nums[i];
            // 计算两数之和为 0的二元组
            int left = i + 1, right = len - 1;
            while(left < right) {
                if (nums[left] + nums[right] > target) {
                    right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    List<Integer> list = new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]));
                    res.add(list);
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            i++;
            while(i < len - 1 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return res;
    }
}